0%

LevelDB源码解析（三）- MemTable解析

Posted on In

前言

在LevelDB中，MemTable其实就是在内存中的一个跳表。

1
private final ConcurrentSkipListMap<InternalKey, Slice> table;

稍等，为什么table的Key不是String，而是InternalKey？

InternalKey

我们看看InternalKey的定义

1
2
3
4
5
6
public class InternalKey
{
    private final Slice userKey;
    private final long sequenceNumber;
    private final ValueType valueType;
}

里面包含三个字段，分别是

  • userKey，就是我们用户增删的key
  • seqNumber是每一次操作的时候，由LevelDB分配的
  • ValueType分为两种，分别是删除和新增。

我们以这个为例

1
2
3
db.put("foo", "v1"); //1
db.put("foo", "v2"); //2
db.delete("foo"); //3
  1. userKey=foo, seqNum = 1, valueType = VALUE
  2. userKey=foo, seqNum = 2, valueType = VALUE
  3. userKey=foo, seqNum = 3, valueType = DELETE

这个时候，我们抛出一个问题，第2条put执行完之后，在MemTable中还有没有internelKey1？

其实这个问题取决于compare方法。

comparator

新建这个跳表的时候，传入的comparator是InternalKeyComparator。

1
2
3
4
5
6
7
8
9
10
InternalKeyComparator#compare
@Override
public int compare(InternalKey left, InternalKey right)
{
    int result = userComparator.compare(left.getUserKey(), right.getUserKey()); //1
    if (result != 0) {
        return result;
    }
    return Long.compare(right.getSequenceNumber(), left.getSequenceNumber()); //2
}
  1. 这里的userComparator是BytewiseComparator，而BytewiseComparator就是简单的比较userKey了。我们三次操作的userKey都是foo，所以这里返回的是0
  2. 进入第二步，就是比较seqNum，seqNum越大的，InternalKey越小，注意，是越小。

所以这里问题解答出来了，执行完这三个语句之后，三个InternalKey都会在跳表中，同时seqNum越大的，排名越靠前。

所以这就导致我们对某个userKey进行search的时候，我们的InternelKey的构造，userKey=foo，seq=currentSeq，valueType=Value。

这样查找的时候，使用ceilingEntry方法查找，这个方法查找的是最近的一个和他一样或者比他大的。

compact

一个MemTable什么时候停止写入，变成磁盘的SSTable呢？

答案在makeRoomForWrite方法中：

1
memTable.approximateMemoryUsage() <= options.writeBufferSize()

这里的options.writeBufferSize，默认情况下是4 << 20，也就是4G。

具体的compact逻辑在compactMemTableInternal方法中，使用tableBuilder，建立SSTable后，加入到VersionSet中。

但是具体加入到哪一个Level中呢？一定就是Level0吗？

答案是不一定。看代码，这里的meta就是新生成SSTable。

1
2
3
4
5
6
7
8
9
int level = 0;
if (meta != null && meta.getFileSize() > 0) {
    Slice minUserKey = meta.getSmallest().getUserKey();
    Slice maxUserKey = meta.getLargest().getUserKey();
    if (base != null) {
        level = base.pickLevelForMemTableOutput(minUserKey, maxUserKey);
    }
    edit.addFile(level, meta);
}

具体放入哪个Level，是由pickLevelForMemTableOutput这个方法决定的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int pickLevelForMemTableOutput(Slice smallestUserKey, Slice largestUserKey) {
    int level = 0;
    if (!overlapInLevel(0, smallestUserKey, largestUserKey)) {
        // Push to next level if there is no overlap in next level,
        // and the #bytes overlapping in the level after that are limited.
        InternalKey start = new InternalKey(smallestUserKey, MAX_SEQUENCE_NUMBER, ValueType.VALUE);
        InternalKey limit = new InternalKey(largestUserKey, 0, ValueType.VALUE);
        while (level < MAX_MEM_COMPACT_LEVEL) {
            if (overlapInLevel(level + 1, smallestUserKey, largestUserKey)) {
                break;
            }
            long sum = Compaction.totalFileSize(versionSet.getOverlappingInputs(level + 2, start, limit));
            if (sum > MAX_GRAND_PARENT_OVERLAP_BYTES) {
                break;
            }
            level++;
        }
    }
    return level;
}

这个方法中，overlapInLevel方法是判断新SSTable的userKey范围是否与这一层的某个文件userKey的范围重合。

如果不重合，就直接下沉到下一个Level进行查找。

图例：MemTable变成了SSTable，范围是13 ~ 18。那么他会放到哪一层呢？

  1. 首先看Level 0，没有一个SSTable的Key范围和他有重合的
  2. 再看Level 1，还是没有一个SSTable的Key范围和他有重合的。
  3. 再次下沉到Level 2，发现第一个SSTable与他有重合。
  4. 所以新的SSTable会被放到Level 1。

最终结果如下图所示。